

#include <iostream>
#include <map>
#include <mutex>
#include <tuple>
#include <type_traits>
#include <unordered_map>

namespace detail {
//递归函数的记忆化包装
//构造函数中使用的哑类，避免与拷贝构造函数的重载冲突
class null_param {};

template <class Sig, class F>
class memoize_helper;

template <class Result, class... Args, class F>
class memoize_helper <Result(Args...), F> {
    private:
        using function_type = F;
        using args_tuple_type 
                = std::tuple<std::decay_t<Args>...>;
        function_type f;
        //定义缓存，因为缓存是可变的，所以要对它的所有修改进行同步
        mutable std::map<args_tuple_type, Result> m_cache;
        mutable std::recursive_mutex m_cache_mutex;
    
    public:
    template <typename Function>
    memoize_helper(Function && f, null_param) : f(f)
    {

    }
    memoize_helper(const memoize_helper& other) : f(other.f)
    {

    }

    template <class... InnerArgs>
    Result operator()(InnerArgs&&... args) const
    {
        std::unique_lock<std::recursive_mutex> lock {m_cache_mutex};

        const auto args_tuple = std::make_tuple(args...);

        const auto cached = m_cache.find(args_tuple);

        if (cached != m_cache.end()) {
            return cached->second;
        } else {
            auto&& result = f(
                *this,
                std::forward<InnerArgs>(args)...);
            m_cache[args_tuple] = result;
            return result;
        }
    }
};
}

using detail::memoize_helper;
template <class Sig, class F>
memoize_helper <Sig, std::decay_t<F>>
make_memoized_r(F&& f)
{
    return {std::forward<F>(f), detail::null_param()};
}
int main(int argc, char *argv[])
{
    auto fibmemo = make_memoized_r<unsigned int(unsigned int)>(
        [] (auto & fib, unsigned int n) {
            std::cout << "Calculating " << n << "!\n";
            return n == 0 ? 0
            : n == 1 ? 1
            : fib(n - 1) + fib(n - 2);
        }
    );
    std::cout << "fib(15) = " << fibmemo(15) << std::endl;
    std::cout << "fib(15) = " << fibmemo(15) << std::endl;
    return 0;
}